/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓CS206␈↓ ∧hFINAL EXAMINATION␈↓ 
0FALL 1977 

␈↓ ↓H␈↓␈↓ α_This␈α
examination␈α
is␈α
open␈α
book␈α
and␈α∞notes.␈α
 Write␈α
LISP␈α
functions␈α
as␈α
follows␈α∞except␈α
where
␈↓ ↓H␈↓something␈α⊂else␈α⊂is␈α⊃requested.␈α⊂ Either␈α⊂notation␈α⊃may␈α⊂be␈α⊂used.␈α⊃ When␈α⊂a␈α⊂requested␈α⊃proof␈α⊂requires
␈↓ ↓H␈↓induction,␈αbe␈αsure␈αand␈α
write␈αdown␈αthe␈αinduction␈αprinciple␈α
appealed␈αto␈αand␈αthe␈α
specific␈αpredicate
␈↓ ↓H␈↓to which the induction is applied.

␈↓ ↓H␈↓1.␈α∞␈↓↓rev␈α
x␈↓␈α∞is␈α
the␈α∞"reverse"␈α
of␈α∞the␈α
arbitrary␈α∞S-expression␈α
␈↓↓x.␈↓␈α∞ Thus␈α
␈↓↓rev␈↓␈α∞(A.(B.C))␈α
=␈α∞((C.B).A).␈α
 Note
␈↓ ↓H␈↓that ␈↓↓rev␈↓ applied to a list does not give the usual reversal of the list.

␈↓ ↓H␈↓␈↓ α_a. Write a recursive definition of ␈↓↓rev.␈↓

␈↓ ↓H␈↓␈↓ α_b. Prove that ␈↓↓rev␈↓ is total.

␈↓ ↓H␈↓␈↓ α_c. Prove that ␈↓↓rev␈↓ satisfies ␈↓↓∀x: rev rev x = x␈↓.

␈↓ ↓H␈↓2.␈αWe␈αwill␈αsay␈αthat␈αa␈αlist␈α␈↓↓u␈↓␈αis␈α"intermittently␈αcontained"␈αin␈αa␈αlist␈α␈↓↓␈↓␈αv␈αif␈αthe␈αelements␈αof␈α␈↓↓u␈↓␈αoccur␈αin␈α␈↓↓v␈↓
␈↓ ↓H␈↓in␈αthe␈α
same␈αorder␈α
as␈αin␈α␈↓↓u␈↓␈α
but␈αpossibly␈α
separated␈αby␈α
other␈αelements␈αof␈α
␈↓↓v.␈↓␈α We␈α
write␈α␈↓↓u ≤≤ v␈↓␈αfor␈α
this
␈↓ ↓H␈↓relation.  Thus we have  (A C E) ≤≤ (X A B C A F D E G).

␈↓ ↓H␈↓␈↓ α_a. Write a recursive definition of ␈↓↓u ≤≤ v␈↓.

␈↓ ↓H␈↓Assume, to make the problem easier, that your ␈↓↓u ≤≤ v␈↓ is total, and prove

␈↓ ↓H␈↓␈↓ α_b. ␈↓↓∀u:u << u␈↓.

␈↓ ↓H␈↓␈↓ α_c. ␈↓↓∀u v w:(u ≤≤ v ∧ v ≤≤ w ⊃ u ≤≤ w)␈↓.

␈↓ ↓H␈↓3.␈α⊂Let␈α⊃␈↓↓e␈↓␈α⊂be␈α⊃a␈α⊂LISP␈α⊂expression␈α⊃in␈α⊂internal␈α⊃notation.␈α⊂ ␈↓↓usecadr␈α⊂e␈↓␈α⊃is␈α⊂equivalent␈α⊃to␈α⊂␈↓↓e␈↓␈α⊃except␈α⊂that
␈↓ ↓H␈↓subexpressions of the form (CAR (CDR ␈↓↓e␈↓)) are replaced by (CADR ␈↓↓e␈↓).  Thus

␈↓ ↓H␈↓␈↓ α_␈↓↓usecadr␈↓ (CONS (CAR (CDR (FOO X))) Y) = (CONS (CADR (FOO X)) Y).

␈↓ ↓H␈↓4. What is ␈↓↓compexp[␈↓(CONS (CAR X) Y), 0, ((X.1)(Y.2))] as compiled by LCOM0 and LCOM4.

␈↓ ↓H␈↓5. Write an abstract evaluator for Boolean expressions using the abstract syntactic functions

␈↓ ↓H␈↓␈↓ α_a. ␈↓↓isand e␈↓ meaning that ␈↓↓e␈↓ has principal connective "and".

␈↓ ↓H␈↓␈↓ α_b. ␈↓↓isor e␈↓ meaning that ␈↓↓e␈↓ has principal connective "or".

␈↓ ↓H␈↓␈↓ α_c. ␈↓↓isnot e␈↓ meaning that ␈↓↓e␈↓ has principal connective "not".

␈↓ ↓H␈↓␈↓ α_d.␈α
In␈α
each␈α
of␈α
the␈α
three␈α
above␈α
cases,␈α␈↓↓operands␈α
e␈↓␈α
gives␈α
a␈α
list␈α
of␈α
the␈α
operands␈α
of␈αthe␈α
expression.
␈↓ ↓H␈↓If␈α␈↓↓e␈↓␈αsatisfies␈α␈↓↓isnot␈↓,␈αthere␈αis␈αexactly␈αone␈αoperand,␈αbut␈αin␈αthe␈αother␈αcases␈αthere␈αmay␈αbe␈αany␈αnumber.
␈↓ ↓H␈↓The LISP functions and predicates ␈↓αa␈↓, ␈↓αd␈↓, ␈↓αn␈↓ are applicable to these lists.

␈↓ ↓H␈↓␈↓ α_e.␈α␈↓↓isvar␈αe␈↓␈αmeans␈αthat␈α␈↓↓e␈↓␈αis␈αa␈αBoolean␈αvariable,␈αand␈αin␈αthis␈αcase␈αthe␈αpredicate␈α␈↓↓true(e,␈↓	x␈↓)␈αis␈αtrue
␈↓ ↓H␈↓if ␈↓↓e␈↓ is true in the state ␈↓	x␈↓.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓␈↓ α_Write␈α∪a␈α∪recursive␈α∪definition␈α∪of␈α∪the␈α∀predicate␈α∪␈↓↓istrue(e,␈↓	x␈↓)␈α∪whose␈α∪value␈α∪is␈α∪true␈α∀or␈α∪false
␈↓ ↓H␈↓according␈α
to␈α
whether␈α
the␈α
Boolean␈α
expression␈α
␈↓↓e␈↓␈α
is␈α
true␈α
in␈α
the␈α
state␈α
␈↓	x␈↓.␈α
 Your␈α
program␈α∞should␈α
not
␈↓ ↓H␈↓look at more terms of "and"s and "or"s than necessary to decide the truth value.